import sun.security.provider.Sun;

import java.util.Random;

public class MaxSonArray {
    //动态规划求最大字段和
    public static int maxSubArray(int[] arr){
        int n=arr.length;
        int[] dp=new int[n+1];
        int Sum=Integer.MIN_VALUE;//先将Sum设置为最小值
        for (int i = 1; i <= n; i++) {
            dp[i]=Math.max(arr[i-1],dp[i-1]+arr[i-1]);
            Sum=Math.max(Sum,dp[i]);
        }
        return Sum;
    }
    //暴力枚举求最大子段和
    public static int maxSubArrayBF(int[] arr){
        int sum=0;
        int n=arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int thisSum=0;
                for (int k = i; k <= j; k++) {
                    thisSum+=arr[k];
                }
                if (thisSum>sum){
                    sum=thisSum;
                }
            }
        }
        return sum;
    }
    // 使用分治法求解最大子数组和
    public static int MaxSubArrDC(int[] arr, int start, int end) {
        // 如果起始位置等于结束位置，表示只有一个元素
        if (start == end) {
            // 如果该元素大于0，则返回该元素，否则返回0
            return arr[start] > 0 ? arr[start] : 0;
        }
        int maxSum; // 最大子数组和
        int mid = (start + end) / 2; // 中间位置
        // 递归求解左半部分的最大子数组和
        int leftMax = MaxSubArrDC(arr, start, mid);
        // 递归求解右半部分的最大子数组和
        int rightMax = MaxSubArrDC(arr, mid + 1, end);
        // 取左半部分和右半部分的最大子数组和的较大值作为初始最大子数组和
        maxSum = Math.max(leftMax, rightMax);
        int left = arr[mid]; // 记录包含中间位置元素的最大子数组和
        int leftSubNum = 0; // 用于记录当前子数组的和
        // 从中间位置向左遍历，计算包含中间位置元素左侧的最大子数组和
        for (int i = mid; i >= start; i--) {
            leftSubNum += arr[i]; // 累加当前元素到子数组和
            left = Math.max(left, leftSubNum); // 更新最大子数组和
        }
        int right = arr[mid + 1]; // 记录包含中间位置右侧元素的最大子数组和
        int rightSubNum = 0; // 用于记录当前子数组的和
        // 从中间位置向右遍历，计算包含中间位置右侧元素的最大子数组和
        for (int i = mid + 1; i <= end; i++) {
            rightSubNum += arr[i]; // 累加当前元素到子数组和
            right = Math.max(right, rightSubNum); // 更新最大子数组和
        }
        // 取左半部分和右半部分的最大子数组和的较大值与包含中间位置的最大子数组和的和的较大值作为最终的最大子数组和
        maxSum = Math.max(maxSum, left + right);
        return maxSum;
    }
    public static void main(String[] args) {
        /*int[] arr=new int[]{1,2,3,4,5,6,7,8,-3};//36 33
        System.out.println("暴力枚举:"+maxSubArrayBF(arr));
        int[] arr1=new int[]{11,22,33,44,55,66,77,-10};//
        System.out.println("动态规划:"+maxSubArray(arr1));
        int[] arr2=new int[]{1,3,5,7,9,11,-3,13,15,-3};//36 33
        System.out.println("分治法:"+MaxSubArrDC(arr2,0,arr2.length-1));*/


        int[] array=new int[2000 ];
        //生成0~2000之间的随机数
        Random random=new Random(501);
        for (int i = 0; i < 500; i++) {

            array[i]= random.nextInt();
        }
        long startTime=System.nanoTime();//记录代码运行前的时间
        maxSubArrayBF(array);
        long endTime=System.nanoTime();//记录代码运行后的时间
        System.out.println("暴力枚举的运行时间为（纳秒）"+(endTime-startTime));
    }
}
